The present invention relates generally to computer implemented system and algorithm for generating a surface from an array of points that have been captured from photographs. More specifically, the present invention relates to a system that generates a highly accurate array of points that can then be used as an effective and accurate tool for surface feature generation and matching in a wide range of applications.
It is well known in the art that there are many tools available for digitizing a three dimensional surface profile. Laser scanner systems, for example, can generate highly accurate surface measurements and 3-D models. The difficulty, however, is that laser scanner systems are prohibitively expensive and require substantial time to process a three dimensional object. Other rendering systems that employ multi-view stereo algorithms generate dense point clouds simply create an array of points that from a computer perspective are disjointed relative to one another. This makes it difficult to near impossible to generate a surface from such a point set. Instead, when the surface is rendered, each point is simply rendered as a disk that is large enough to overlap the adjacent point in a manner that provides the appearance of a surface.
Due to the cost and time investment required in the art in obtaining the array of points, structured-light systems are the preferred choice for do-it yourself 3D scanning applications. They are easy to deploy, only an off-the-shelf data projector and camera are required. Further, they are very accurate when implemented carefully. A projector-camera pair works as a stereo system, with the advantage that a properly chosen projected pattern simplifies the task of finding point correspondences. In such systems, projectors are modeled as inverse cameras and all considerations known for passive stereo systems may be applied with almost no change. However, the calibration procedure must be adapted to the fact that projectors cannot directly measure the pixel coordinates of 3D points projected onto the projector image plane as cameras do. Viewpoint, zoom, focus, and other parameters ought to be adjusted, both in projector and camera, to match each target object size and scanning distance; invalidating any previous calibration. Therefore, structured-light systems must first be calibrated before each use in order to guarantee the best result. As a result, the simplicity of the calibration procedure becomes as valuable as its precision.
Many projector calibration procedures exist, however, none of the available methods are easy for the common user to perform. Further, they generally require high precision to enable accurate 3D reconstructions. Several methods use a pre-calibrated camera to find world coordinates in some calibration artifact, which in turn they use to assign projector correspondences. These methods might be simple to perform, but all of them lack of accuracy in the projector parameters due to their dependence on the camera calibration. The inaccuracies are a direct consequence of their approach: even small camera calibration errors could result into large world coordinate errors. Their failure point is in estimating the projector parameters from the, far from accurate, world coordinates decreasing the complete system precision.
A different approach employs movement of the projector to several locations so that the calibration pattern, projected onto a fixed plane, changes its shape. However, moving the projector is generally inconvenient or impossible (e.g. a system mounted on a rig). Moreover, these methods are not applicable if a metric reconstruction is mandatory because their result is only up-to-scale.
Other proposed algorithms employ a projected pattern that is iteratively adjusted until it overlaps a printed pattern. The overlap is measured with help of an un-calibrated camera. Since both patterns must be clearly identified, the classic black and white pattern is replaced by color versions of it, making color camera mandatory. In practice, switching to color patterns makes color calibration unavoidable as printed and camera colors seldom match, thereby imposing an extra requirement to the user.
Another common practice among projector calibration methods is to find one homography transformation between a calibration plane and the projector image plane. Despite the elegance of the concept, they cannot model non-linear distortions as the ones introduced by projector lenses.
Some methods claim to get very accurate results by projecting patterns on a flat aluminum board mounted on a high precision moving mechanism. However, such a special equipment is not available to the common user, limiting its general applicability. We disregard this method as non-practical. While others employ structured-light patterns to create new synthetic images from the projector's viewpoint and feed them to standard camera calibration tools. The intermediate step of creating synthetic images at the projector's resolution, usually low, might discard important information.
There is therefore a need for a method and system for inexpensively and reliably generating a complete and accurate array of 3-D points from photographs. There is a further need for a method and system that generates an accurate set of 3-D points for further use in surface representation that can be employed for feature matching relative to a database of known surfaces.